package solution1.demo_2023_10;

<<<<<<< HEAD:demo_2023_10/Solution.java
//import javafx.util.Pair;
//
//import java.lang.reflect.Proxy;
//import java.util.*;
//
//class ListNode {
//     int val;
//     ListNode next;
//     ListNode() {}
//     ListNode(int val) { this.val = val; }
//     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
// }
//
//class Node {
//    int val;
//    Node next;
//    Node random;
//
//    public Node(int val) {
//        this.val = val;
//        this.next = null;
//        this.random = null;
//    }
//}
//
//
//public class Solution {
//
////    //1.反转链表
////    public ListNode reverseList(ListNode head) {
////        if(head == null) {
////            return head;
////        }
////        ListNode cur = head.next;
////        head.next = null;
////        while(cur != null) {
////            ListNode curNext = cur.next;
////            cur.next = head;
////            head = cur;
////            cur = curNext;
////        }
////        return head;
////    }
//
//    //2.两两交换链表中的节点
//    public ListNode swapPairs(ListNode head) {
//        if(head == null || head.next == null) {
=======

import java.lang.reflect.Proxy;
import java.util.*;

class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}


public class Solution {

//    //1.反转链表
//    public ListNode reverseList(ListNode head) {
//        if(head == null) {
>>>>>>> ff3f488e325d7766c3bd91ad5d1691e123de9b38:solution1/demo_2023_10/Solution.java
//            return head;
//        }
//        //假节点
//        ListNode dummy = new ListNode();
//        dummy.next = head;
//        ListNode prev = dummy;
//        while(head != null && head.next != null) {
//            ListNode cur = head.next;
//            prev.next = cur;
//            head.next = cur.next;
//            cur.next = head;
//            prev = head;
//            head = head.next;
//        }
//        return dummy.next;
//    }
//
//    //3.删除链表的倒数第 N 个结点
//    public ListNode removeNthFromEnd(ListNode head, int n) {
//        if(head.next == null && n == 1) {
//            return null;
//        }
//        ListNode fast = head;
//        ListNode slow = head;
//        int index = n;
//        while(index != 0) {
//            fast = fast.next;
//            index--;
//        }
//        ListNode dummy = new ListNode();
//        dummy.next = head;
//        ListNode prev = dummy;
//        while(fast != null) {
//            prev = slow;
//            fast = fast.next;
//            slow = slow.next;
//        }
//        prev.next = slow.next;
//        return dummy.next;
//    }
//
//    private ListNode getResult(ListNode fast, ListNode slow, int ans) {
//        while(ans != 0) {
//            fast = fast.next;
//            ans--;
//        }
//        //两个一起
//        while(fast != slow) {
//            fast = fast.next;
//            slow = slow.next;
//        }
//        return fast;
//    }
//
//
//    //4.面试题 02.07. 链表相交
//    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//        if(headA == null || headB == null) {
//            return null;
//        }
//        ListNode cur1 = headA;
//        ListNode cur2 = headB;
//        int len1 = 0;
//        int len2 = 0;
//        while(cur1 != null) {
//            cur1 = cur1.next;
//            len1++;
//        }
//        while(cur2 != null) {
//            cur2 = cur2.next;
//            len2++;
//        }
//        cur1 = headA;
//        cur2 = headB;
//        int ans = len1 > len2 ? len1 - len2 : len2 - len1;
//        ListNode result = null;
//        if(len1 > len2) {
//            result = getResult(cur1, cur2, ans);
//        } else {
//            result = getResult(cur2, cur1, ans);
//        }
//        return result;
//    }
//
//    //5.环形链表2
//    public ListNode detectCycle(ListNode head) {
//        if(head == null || head.next == null) {
//            return null;
//        }
//        ListNode fast = head.next.next;
//        ListNode slow = head.next;
//        while(fast != null && fast.next != null && fast != slow) {
//            fast = fast.next.next;
//            slow = slow.next;
//        }
//        if(fast == null || fast.next == null) {
//            return null;
//        }
//        ListNode cur = head;
//        while(slow != cur) {
//            slow = slow.next;
//            cur = cur.next;
//        }
//        return cur;
//    }
//
//    //6.重排链表
//    private ListNode reverseList(ListNode head) {
//        ListNode cur = head.next;
//        head.next = null;
//        while(cur != null) {
//            ListNode curNext = cur.next;
//            cur.next = head;
//            head = cur;
//            cur = curNext;
//        }
//        return head;
//    }
//
//    public void reorderList(ListNode head) {
//        if(head.next == null || head.next.next == null) {
//            return;
//        }
//        ListNode fast = head;
//        ListNode slow = head;
//        ListNode prev = null;
//        while(fast != null && fast.next != null) {
//            prev = slow;
//            fast = fast.next.next;
//            slow = slow.next;
//        }
//        //分割
//        prev.next = null;
//        //将后半段链表反转
//        ListNode cur2 = reverseList(slow);
//        //连接两个链表
//        ListNode cur1 = head;
//        while(cur1 != null && cur2 != null) {
//            ListNode curNext1 = cur1.next;
//            ListNode curNext2 = cur2.next;
//            cur1.next = cur2;
//            cur2.next = curNext1;
//            prev = cur2;
//            cur1 = curNext1;
//            cur2 = curNext2;
//        }
//        if(cur1 == null && cur2 != null) {
//            prev.next = cur2;
//        }
//    }
//
//    //7.双栈模拟队列
//    class MyQueue {
//
//        private Stack<Integer> stack1;
//        private Stack<Integer> stack2;
//
//        public MyQueue() {
//            this.stack1 = new Stack<>();
//            this.stack2 = new Stack<>();
//        }
//
//        public void push(int x) {
//            while(!stack2.isEmpty()) {
//                stack1.push(stack2.pop());
//            }
//            stack1.push(x);
//        }
//
//        public int pop() {
//            while(!stack1.isEmpty()) {
//                stack2.push(stack1.pop());
//            }
//            return stack2.pop();
//        }
//
//        public int peek() {
//            while(!stack1.isEmpty()) {
//                stack2.push(stack1.pop());
//            }
//            return stack2.peek();
//        }
//
//        public boolean empty() {
//            return stack1.isEmpty() && stack2.isEmpty();
//        }
//    }
//
//
//    //8.用队列实现栈
//    class MyStack {
//
//        private Queue<Integer> queue;
//
//        public MyStack() {
//            this.queue = new LinkedList<>();
//        }
//
//        public void push(int x) {
//            queue.offer(x);
//            for(int i = 0; i < queue.size() - 1; i++) {
//                queue.offer(queue.poll());
//            }
//        }
//
//        public int pop() {
//            return queue.poll();
//        }
//
//        public int top() {
//            return queue.peek();
//        }
//
//        public boolean empty() {
//            return queue.isEmpty();
//        }
//    }
//
//    //9.有效的括号
//    public boolean isValid(String s) {
//        Stack<Character> stack = new Stack<>();
//        for(int i = 0; i < s.length(); i++) {
//            char ch = s.charAt(i);
//            if(stack.isEmpty()) {
//                stack.push(ch);
//            } else if(ch == '(' || ch == '[' ||
//                    ch == '{') {
//                stack.push(ch);
//            } else {
//                if(stack.isEmpty()) {
//                    return false;
//                }
//                char sh = stack.peek();
//                if((sh == '(' && ch == ')') ||
//                        (sh == '[' && ch == ']') ||
//                        (sh == '{' && ch == '}')) {
//                    stack.pop();
//                } else {
//                    return false;
//                }
//            }
//        }
//        return stack.isEmpty();
//    }
//
//    //10.删除字符串中的所有相邻重复项
//    public String removeDuplicates(String s) {
//        Stack<Character> stack = new Stack<>();
//        for(int i = 0; i < s.length(); i++) {
//            char ch = s.charAt(i);
//            if(stack.isEmpty()) {
//                stack.push(ch);
//            } else if(stack.peek() == ch) {
//                stack.pop();
//            } else {
//                stack.push(ch);
//            }
//        }
//        StringBuilder stringBuilder = new StringBuilder();
//        while(!stack.isEmpty()) {
//            stringBuilder.append(stack.pop());
//        }
//        return stringBuilder.reverse().toString();
//    }
//
//    //11.逆波兰表达式求值
//    public int evalRPN(String[] tokens) {
//        Stack<Integer> stack = new Stack<>();
//        for(int i = 0; i < tokens.length; i++) {
//            String str = tokens[i];
//            char ch = str.charAt(0);
//            if(ch == '+' || (ch == '-' && str.length() == 1) || ch == '*' || ch == '/') {
//                int b = stack.pop();
//                int a = stack.pop();
//                switch(ch) {
//                    case '+':
//                        stack.push(a + b);
//                        break;
//                    case '-':
//                        stack.push(a - b);
//                        break;
//                    case '*':
//                        stack.push(a * b);
//                        break;
//                    case '/':
//                        stack.push(a / b);
//                        break;
//                }
//            } else {
//                stack.push(Integer.parseInt(str));
//            }
//        }
//        return stack.pop();
//    }
//
//    //12. 滑动窗口最大值
//    public int[] maxSlidingWindow(int[] nums, int k) {
//        //1.维护一个单调递增队列
//        Deque<Integer> deque = new LinkedList<>();
//        int[] result = new int[nums.length - k + 1];
//        int index = 0;
//        for(int i = 0; i < nums.length; i++) {
//            if(i < k) {
//                while(!deque.isEmpty() && deque.peekLast() < nums[i]) {
//                    deque.pollLast();
//                }
//                deque.offerLast(nums[i]);
//            } else {
//                //1.记录最大元素(左端)
//                result[index++] = deque.peekFirst();
//                //2.踢出元素
//                int toDel = nums[i - k];
//                if(!deque.isEmpty() && deque.peekFirst() == toDel) {
//                    deque.pollFirst();
//                }
//                //3.加入新元素
//                while(!deque.isEmpty() && deque.peekLast() < nums[i]) {
//                    deque.pollLast();
//                }
//                deque.offerLast(nums[i]);
//            }
//        }
//        result[index] = deque.peekFirst();
//        return result;
//    }
//
//    //13.前 K 个高频元素
//    public int[] topKFrequent(int[] nums, int k) {
//        //1.计算频率
//        Map<Integer, Integer> map = new HashMap<>();
//        for(int i = 0; i < nums.length; i++) {
//            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
//        }
//        //2.建立一个小根堆
//        PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>(new Comparator<Map.Entry<Integer, Integer>>() {
//            @Override
//            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
//                return o1.getValue() - o2.getValue();
//            }
//        });
//        for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
//            if(queue.size() < k) {
//                queue.offer(entry);
//            } else {
//                if(queue.peek().getValue() < entry.getValue()) {
//                    queue.poll();
//                    queue.offer(entry);
//                }
//            }
//        }
//        int[] result = new int[k];
//        int index = 0;
//        while(!queue.isEmpty()) {
//            result[index++] = queue.poll().getKey();
//        }
//        return result;
//    }
//
//    //14.链表排序
//    public ListNode sortList(ListNode head) {
//        if(head == null || head.next == null) {
//            return head;
//        }
//        return mergeSort(head);
//    }
//
//    private ListNode mergeSort(ListNode head) {
//        if(head.next == null) {
//            return head;
//        }
//        ListNode fast = head;
//        ListNode slow = head;
//        ListNode mid = null;
//        while(fast != null && fast.next != null) {
//            fast = fast.next.next;
//            mid = slow;
//            slow = slow.next;
//        }
//        //拆分
//        mid.next = null;
//        ListNode left = mergeSort(head);
//        ListNode right = mergeSort(slow);
//        //合并
//        return merge(left, right);
//    }
//
//    private ListNode merge(ListNode left, ListNode right) {
//        ListNode dummy = new ListNode();
//        ListNode cur = dummy;
//        while(left != null && right != null) {
//            if(left.val > right.val) {
//                cur.next = right;
//                right = right.next;
//            } else {
//                cur.next = left;
//                left = left.next;
//            }
//            cur = cur.next;
//        }
//        if(left != null) {
//            cur.next = left;
//        }
//        if(right != null) {
//            cur.next = right;
//        }
//        return dummy.next;
//    }
//
//
//    //15.二叉树的最近公共祖先
//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        if(root == null) {
//            return null;
//        }
//        if(root == p || root == q) {
//            return root;
//        }
//        TreeNode left = lowestCommonAncestor(root.left, p, q);
//        TreeNode right = lowestCommonAncestor(root.right, p, q);
//        if(left != null && right != null) {
//            return root;
//        } else if(left != null && right == null) {
//            return left;
//        } else if(left == null && right != null) {
//            return right;
//        } else {
//            return null;
//        }
//    }
//
//    //16.从中序与后序遍历序列构造二叉树
//    private TreeNode dfs(int[] inorder, int[] postorder, int left, int right) {
//        if(left > right) {
//            return null;
//        }
//        TreeNode root = new TreeNode(postorder[index--]);
//        int rootIndex = fundRoot(root.val, inorder);
//        root.right = dfs(inorder, postorder, rootIndex + 1, right);
//        root.left = dfs(inorder, postorder, left, rootIndex - 1);
//        return root;
//    }
//
//    private int fundRoot(int target, int[] inorder) {
//        for(int i = 0; i < inorder.length; i++) {
//            if(inorder[i] == target) {
//                return i;
//            }
//        }
//        return -1;
//    }
//
//
//    private int index;
//    public TreeNode buildTree(int[] inorder, int[] postorder) {
//        this.index = inorder.length - 1;
//        return dfs(inorder, postorder, 0, inorder.length - 1);
//    }
//
//
//    //17.将有序数组转换为二叉搜索树
//    private TreeNode dfs(int[] nums, int left, int right) {
//        if(left > right) {
//            return null;
//        }
//        int index = (right + left) / 2;
//        TreeNode root = new TreeNode(nums[index]);
//        root.left = dfs(nums, left, index - 1);
//        root.right = dfs(nums, index + 1, right);
//        return root;
//    }
//
//    public TreeNode sortedArrayToBST(int[] nums) {
//        return dfs(nums, 0, nums.length - 1);
//    }
//
//
//    //18.链表排序
////    private ListNode merge(ListNode left, ListNode right) {
////        ListNode dummy = new ListNode();
////        ListNode cur = dummy;
////        while(left != null && right != null) {
////            if(left.val < right.val) {
////                cur.next = left;
////                left = left.next;
////            } else {
////                cur.next = right;
////                right = right.next;
////            }
////            cur = cur.next;
////        }
////        if(left != null) {
////            cur.next = left;
////        }
////        if(right != null) {
////            cur.next = right;
////        }
////        return dummy.next;
////    }
////
////    private ListNode mergeSort(ListNode head) {
////        if(head.next == null) {
////            return head;
////        }
////        ListNode fast = head;
////        ListNode slow = head;
////        ListNode mid = null;
////        while(fast != null && fast.next != null) {
////            fast = fast.next.next;
////            mid = slow;
////            slow = slow.next;
////        }
////        mid.next = null;
////        ListNode left = mergeSort(head);
////        ListNode right = mergeSort(slow);
////        return merge(left, right);
////    }
////
////    public ListNode sortList(ListNode head) {
////        if(head == null || head.next == null) {
////            return head;
////        }
////        return mergeSort(head);
////    }
//
//    //19.将有序数组转换为二叉搜索树
////    private TreeNode dfs(int[] nums, int left, int right) {
////        if(left > right) {
////            return null;
////        }
////        int mid = (left + right) / 2;
////        TreeNode root = new TreeNode(nums[mid]);
////        root.left = dfs(nums, left, mid - 1);
////        root.right = dfs(nums, mid + 1, right);
////        return root;
////    }
////
////    public TreeNode sortedArrayToBST(int[] nums) {
////        return dfs(nums, 0, nums.length - 1);
////    }
//
//    //20.爬楼梯
//    public int climbStairs(int n) {
//        int[] dp = new int[n + 1];
//        dp[0] = 1;
//        dp[1] = 1;
//        for(int i = 2; i <= n; i++) {
//            dp[i] = dp[i - 1] + dp[i - 2];
//        }
//        return dp[n];
//    }
//
//    //21.使用最小花费爬楼梯
//    public int minCostClimbingStairs(int[] cost) {
//        //爬上 i 个台阶，最少花费 cost[i]
//        //dp[0] = 1
//        //dp[1] = 1  1 || 100
//        //dp[2] = 2  (1||100) 1  ||  100
//        //dp[3] = 2  dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
//        int len = cost.length;
//        int[] dp = new int[len + 1];
//        dp[0] = 0;
//        dp[1] = 0;
//        for(int i = 2; i <= len; i++) {
//            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
//        }
//        return dp[len];
//    }
//
//    //22.不同路径
//    public int uniquePaths(int m, int n) {
//        int[][] dp = new int[m][n];
//        for(int i = 0; i < n; i++) {
//            dp[0][i] = 1;
//        }
//        for(int j = 0; j < m; j++) {
//            dp[j][0] = 1;
//        }
//        for(int i = 1; i < m; i++) {
//            for(int j = 1; j < n; j++) {
//                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
//            }
//        }
//        return dp[m - 1][n - 1];
//    }
//
//    //23.不同路径 II
//    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
//        int row = obstacleGrid.length;
//        int col = obstacleGrid[0].length;
//        int[][] dp = new int[row][col];
//        for(int i = 0; i < row; i++) {
//            if(obstacleGrid[i][0] == 1) {
//                break;
//            }
//            dp[i][0] = 1;
//        }
//        for(int j = 0; j < col; j++) {
//            if(obstacleGrid[0][j] == 1) {
//                break;
//            }
//            dp[0][j] = 1;
//        }
//        for(int i = 1; i < row; i++) {
//            for(int j = 1; j < col; j++) {
//                if(obstacleGrid[i][j] == 1) {
//                    continue;
//                }
//                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
//            }
//        }
//        return dp[row - 1][col - 1];
//    }
//
//    //24.整数拆分
//    public int integerBreak(int n) {
//        //1.状态: 最大乘积 dp[i];
//        int[] dp = new int[n + 1];
//        dp[2] = 1;
//        for(int i = 3; i <= n; i++) {
//            for(int j = 1; j < i - 1; j++) {
//                dp[i] = Math.max(dp[i], Math.max(dp[i - j] * j, (i - j) * j));
//            }
//        }
//        return dp[n];
//    }
//
//
//    //25.使用最小花费爬楼梯
////    public int minCostClimbingStairs(int[] cost) {
////        int len = cost.length;
////        int[] dp = new int[len + 1];
////        dp[0] = 0;
////        dp[1] = 0;
////        for(int i = 2; i <= len; i++) {
////            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
////        }
////        return dp[len];
////    }
//
//    //26.分割等和子集
//    public boolean canPartition(int[] nums) {
//        //背包的容量相当于是数组整体数值之和的一半 capacity
//        //问题转化位从 nums 中取出 i 个商品，装满容量为 capacity 的背包最大的商品数量最大价值
//        //最大价值就是 nums 对应的值
//        //最后只需要比较最大价值是否等于 capacity
//        int len = nums.length;
//        int capacity = 0;
//        for(int i = 0; i < len; i++) {
//            capacity += nums[i];
//        }
//        if(capacity % 2 != 0) {
//            return false;
//        }
//        capacity /= 2;
//        int[] dp = new int[capacity + 1];
//        for(int i = 0; i < len; i++) {
//            for(int j = capacity; j >= nums[i]; j--) {
//                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
//            }
//        }
//        return dp[capacity] == capacity;
//    }
//
//    //27.最后一块石头的重量 II
//    public int lastStoneWeightII(int[] stones) {
//        int len = stones.length;
//        int capacity = 0;
//        int sum = 0;
//        for(int stone : stones) {
//            sum += stone;
//        }
//        capacity = sum / 2;
//        int[] dp = new int[capacity + 1];
//        for(int i = 0; i < len; i++) {
//            for(int j = capacity; j >= stones[i]; j--) {
//                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
//            }
//        }
//        return sum - dp[capacity] - dp[capacity];
//    }
//
//    //28.目标和
//    public int findTargetSumWays(int[] nums, int target) {
//        //假设 x 为和，那么差就是 sum - x
//        //x - (sum - x) = target;
//        //x = (target + sum) / 2
//        int len = nums.length;
//        int sum = 0;
//        for(int i = 0; i < len; i++) {
//            sum += nums[i];
//        }
//        if((target + sum) % 2 != 0) { //无解
//            return 0;
//        }
//        if(target > sum || -target > sum) {
//            return 0;
//        }
//        int x = (target + sum) / 2;
//        int[] dp = new int[x + 1];
//        dp[0] = 1;
//        for(int i = 0; i < len; i++) {
//            for(int j = x; j >= nums[i]; j--) {
//                dp[j] = dp[j] + dp[j - nums[i]];
//            }
//        }
//        return dp[x];
//    }
//
//    //29.一和零
//    public int findMaxForm(String[] strs, int m, int n) {
//        int[][] dp = new int[m + 1][n + 1];
//        for(int i = 0; i < strs.length; i++) {
//            int sum0 = 0;
//            int sum1 = 0;
//            for(int j = 0; j < strs[i].length(); j++) {
//                if(strs[i].charAt(j) == '0') {
//                    sum0++;
//                } else {
//                    sum1++;
//                }
//            }
//            for(int j = m; j >= sum0; j--) {
//                for(int k = n; k >= sum1; k--) {
//                    dp[j][k] = Math.max(dp[j][k], dp[j - sum0][k - sum1] + 1);
//                }
//            }
//        }
//        return dp[m][n];
//    }
//
//    //30.零钱兑换 II
//    public int change(int amount, int[] coins) {
//        int[] dp = new int[amount + 1];
//        dp[0] = 1;
//        for(int i = 0; i < coins.length; i++) { //物品
//            for(int j = coins[i]; j <= amount; j++) {
//                dp[j] = dp[j] + dp[j - coins[i]];
//            }
//        }
//        return dp[amount];
//    }
//
//    //31.组合总和 Ⅳ
//    public int combinationSum4(int[] nums, int target) {
//        int[] dp = new int[target + 1];
//        dp[0] = 1;
//        for(int j = 0; j <= target; j++) {
//            for(int i = 0; i < nums.length; i++) { //物品
//                if(j >= nums[i]) {
//                    dp[j] = dp[j] + dp[j - nums[i]];
//                }
//            }
//        }
//        return dp[target];
//    }
//
//    //32.零钱兑换
//    public int coinChange(int[] coins, int amount) {
//        int max = Integer.MAX_VALUE;
//        int[] dp = new int[amount + 1];
//        Arrays.fill(dp, max);
//        dp[0] = 0;
//        for(int i = 0; i < coins.length; i++) {
//            for(int j = coins[i]; j <= amount; j++) {
//                if(dp[j - coins[i]] != max) {
//                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
//                }
//            }
//        }
//        return dp[amount] == max ? -1 : dp[amount];
//    }
//
//    //33.完全平方数
//    public int numSquares(int n) {
//        int max = Integer.MAX_VALUE;
//        int[] dp = new int[n + 1];
//        Arrays.fill(dp, max);
//        dp[0] = 0;
//        for(int i = 1; i <= n; i++) {
//            for(int j = i*i; j <= n; j++) {
//                dp[j] = Math.min(dp[j], dp[j - i*i] + 1);
//            }
//        }
//        return dp[n];
//    }
//
//    //34.单词拆分
//    public boolean wordBreak(String s, List<String> wordDict) {
//        int len = s.length();
//        boolean[] dp = new boolean[len + 1];
//        dp[0] = true;
//        for(int i = 1; i <= len; i++) {
//            for(int j = 0; j < i; j++) {
//                String str = s.substring(j, i);
//                if(dp[j] == true && wordDict.contains(str)) {
//                    dp[i] = true;
//                }
//            }
//        }
//        return dp[len];
//    }
//
//    //35.打家劫舍
////    public int rob(int[] nums) {
////        int len = nums.length;
////        int[] dp = new int[len + 1];
////
////        dp[0] = 0;
////        dp[1] = nums[0];
////        for(int i = 2; i <= len; i++) {
////            dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
////        }
////        return dp[len];
////    }
//
////    //36.打家劫舍II
////    private int robPlay(int[] nums) {
////        int len = nums.length;
////        int[] dp = new int[len + 1];
////        dp[1] = nums[0];
////        for(int i = 2; i <= len; i++) {
////            dp[i] = Math.max(dp[i - 2] + nums[i - 1], dp[i - 1]);
////        }
////        return dp[len];
////    }
////
////    public int rob(int[] nums) {
////        int len = nums.length;
////        if(len == 1) {
////            return nums[0];
////        }
////        int left = robPlay(Arrays.copyOfRange(nums, 0, len - 1));
////        int right = robPlay(Arrays.copyOfRange(nums, 1, len));
////        return left > right ? left : right;
////    }
//
//    //打家劫舍III
//    public int rob(TreeNode root) {
//        Pair<Integer, Integer> pair = dfs(root);
//        return Math.max(pair.getKey(), pair.getValue());
//    }
<<<<<<< HEAD:demo_2023_10/Solution.java
=======

//    //打家劫舍III
//    public int rob(TreeNode root) {
//        Pair<Integer, Integer> pair = dfs(root);
//        return Math.max(pair.getKey(), pair.getValue());
//    }
>>>>>>> ff3f488e325d7766c3bd91ad5d1691e123de9b38:solution1/demo_2023_10/Solution.java
//
//    public Pair<Integer, Integer> dfs(TreeNode root) {
//        if(root == null) {
//            return new Pair<>(0, 0);
//        }
//        Pair<Integer, Integer> left = dfs(root.left);
//        Pair<Integer, Integer> right = dfs(root.right);
//        //1.偷当前节点
//        int val1 = root.val + left.getKey() + right.getKey();
//        //2.不偷当前节点
//        int val2 = Math.max(left.getKey(), left.getValue()) +
//                Math.max(right.getKey(), right.getValue());
//        return new Pair<>(val2, val1);
//    }
<<<<<<< HEAD:demo_2023_10/Solution.java
//
//    //37.买卖股票的最佳时机
//    public int maxProfit1(int[] prices) {
//        int len = prices.length;
//        int[][] dp = new int[len][2];
//        dp[0][0] = -prices[0];
//        dp[0][1] = 0;
//        for(int i = 1; i < len; i++) {
//            dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
//            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
//        }
//        return dp[len - 1][1];
//    }
//
//    //38.买卖股票的最佳时机II
//    public int maxProfit2(int[] prices) {
//        //dp[i][0]: max(dp[i - 1][0], dp[i - 1][1] - prices[i])
//        //dp[i][1]: max(dp[i - 1][1], dp[i - 1][0] + prices[i])
//        int len = prices.length;
//        int[][] dp = new int[len][2];
//        dp[0][0] = -prices[0];
//        dp[0][1] = 0;
//        for(int i = 1; i < len; i++) {
//            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
//            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
//        }
//        return dp[len - 1][1];
//    }
//
//    //39.买卖股票的最佳时机III
//    public int maxProfit3(int[] prices) {
//        //dp[i][0]: 前i天什么都不干
//        //dp[i][1]: 第一次持有股票
//        //dp[i][2]: 第一次不持有股票
//        //dp[i][3]: 第二次持有股票
//        //dp[i][4]: 第二次不持有股票
//        int len = prices.length;
//        int[][] dp = new int[len][5];
//        dp[0][0] = 0;
//        dp[0][1] = -prices[0];
//        dp[0][2] = 0;
//        dp[0][3] = -prices[0];
//        dp[0][4] = 0;
//        for(int i = 1; i < len; i++) {
//            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
//            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
//            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
//            dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
//        }
//        return Math.max(dp[len - 1][2], dp[len - 1][4]);
//    }
//
//    //40.买卖股票的最佳时机IV
//    public int maxProfit(int k, int[] prices) {
//        int ans = 2 * k + 1;
//        int len = prices.length;
//        int[][] dp = new int[len][ans];
//        for(int i = 0; i < ans; i++) {
//            dp[0][i] = i % 2 == 0 ? 0 : -prices[0];
//        }
//        for(int i = 1; i < len; i++) {
//            for(int j = 1; j < ans; j++) {
//                if(j % 2 == 1) {
//                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
//                } else {
//                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
//                }
//            }
//        }
//        int result = 0;
//        for(int i = 2; i < ans; i += 2) {
//            result = Math.max(result, dp[len - 1][i]);
//        }
//        return result;
//    }
//
//    //41.买卖股票的最佳时机含冷冻期
//    public int maxProfit(int[] prices) {
//        //dp[i][0](持有): Math.max(dp[i - 1][0], Math.max(dp[i - 1][3], dp[i - 1][2]) - prices[i]);
//        //dp[i][1](当天卖出股票): dp[i - 1][0] + prices[i];
//        //dp[i][2](冷冻期): dp[i - 1][1];
//        //dp[i][3](冷冻期后不持股): Math.max(dp[i - 1][3], dp[i - 1][2]);
//        int len = prices.length;
//        int[][] dp = new int[len][4];
//        dp[0][0] = -prices[0];
//        dp[0][1] = 0;
//        dp[0][2] = 0;
//        dp[0][3] = 0;
//        for(int i = 1; i < len; i++) {
//            dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][3], dp[i - 1][2]) - prices[i]);
//            dp[i][1] = dp[i - 1][0] + prices[i];
//            dp[i][2] = dp[i - 1][1];
//            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2]);
//        }
//        return Math.max(dp[len - 1][1], Math.max(dp[len - 1][2], dp[len - 1][3]));
//    }
//
//    //42.最长递增子序列
//    public int lengthOfLIS(int[] nums) {
//        //dp[i]: 以 nums[i] 为结尾的，最长严格递增子序列长度
//        //dp[i] = Math.max(dp[j] + 1, dp[i]);
//        int len = nums.length;
//        int[] dp = new int[len];
//        Arrays.fill(dp, 1);
//        int result = 1;
//        for(int i = 1; i < len; i++) {
//            for(int j = 0; j < i; j++) {
//                if(nums[j] < nums[i]) {
//                    dp[i] = Math.max(dp[j] + 1, dp[i]);
//                }
//            }
//            result = result > dp[i] ? result : dp[i];
//        }
//        return result;
//    }
//
//    //43.最长连续递增序列
//    public int findLengthOfLCIS(int[] nums) {
//        //dp[i]: 以 nums[i] 为结尾的最长连续递增序列
//        int len = nums.length;
//        int[] dp = new int[len];
//        Arrays.fill(dp, 1);
//        int result = 1;
//        for(int i = 1; i < len; i++) {
//            if(nums[i - 1] < nums[i]) {
//                dp[i] = dp[i - 1] + 1;
//            }
//            result = result > dp[i] ? result : dp[i];
//        }
//        return result;
//    }
//
//    //44.随机链表的复制
//    public Node copyRandomList(Node head) {
//        Node dummy = new Node(0);
//        Node cur = dummy;
//        Node cur2 = head;
//        Map<Node, Node> map = new HashMap<>();
//        //1.先用 map 记录一遍
//        while(cur2 != null) {
//            Node node = new Node(cur2.val);
//            cur.next = node;
//            cur = cur.next;
//            map.put(cur2, cur);
//            cur2 = cur2.next;
//        }
//        //2.写随机指针
//        cur = dummy.next;
//        cur2 = head;
//        while(cur != null) {
//            Node target = map.get(cur2.random);
//            cur.random = target;
//            cur = cur.next;
//            cur2 = cur2.next;
//        }
//        return dummy.next;
//    }
//
//}
//
//class Main {
//    //测试
//    public static void main(String[] args) {
//        Solution solution = new Solution();
//        int[] coins = {1,2,5};
//        System.out.println(Arrays.toString(coins));
//        int amount = 11;
//        solution.coinChange(coins, amount);
//    }
//}
=======

    //37.买卖股票的最佳时机
    public int maxProfit1(int[] prices) {
        int len = prices.length;
        int[][] dp = new int[len][2];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for(int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[len - 1][1];
    }

    //38.买卖股票的最佳时机II
    public int maxProfit2(int[] prices) {
        //dp[i][0]: max(dp[i - 1][0], dp[i - 1][1] - prices[i])
        //dp[i][1]: max(dp[i - 1][1], dp[i - 1][0] + prices[i])
        int len = prices.length;
        int[][] dp = new int[len][2];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for(int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[len - 1][1];
    }

    //39.买卖股票的最佳时机III
    public int maxProfit3(int[] prices) {
        //dp[i][0]: 前i天什么都不干
        //dp[i][1]: 第一次持有股票
        //dp[i][2]: 第一次不持有股票
        //dp[i][3]: 第二次持有股票
        //dp[i][4]: 第二次不持有股票
        int len = prices.length;
        int[][] dp = new int[len][5];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][2] = 0;
        dp[0][3] = -prices[0];
        dp[0][4] = 0;
        for(int i = 1; i < len; i++) {
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
            dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
        }
        return Math.max(dp[len - 1][2], dp[len - 1][4]);
    }

    //40.买卖股票的最佳时机IV
    public int maxProfit(int k, int[] prices) {
        int ans = 2 * k + 1;
        int len = prices.length;
        int[][] dp = new int[len][ans];
        for(int i = 0; i < ans; i++) {
            dp[0][i] = i % 2 == 0 ? 0 : -prices[0];
        }
        for(int i = 1; i < len; i++) {
            for(int j = 1; j < ans; j++) {
                if(j % 2 == 1) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i]);
                }
            }
        }
        int result = 0;
        for(int i = 2; i < ans; i += 2) {
            result = Math.max(result, dp[len - 1][i]);
        }
        return result;
    }

    //41.买卖股票的最佳时机含冷冻期
    public int maxProfit(int[] prices) {
        //dp[i][0](持有): Math.max(dp[i - 1][0], Math.max(dp[i - 1][3], dp[i - 1][2]) - prices[i]);
        //dp[i][1](当天卖出股票): dp[i - 1][0] + prices[i];
        //dp[i][2](冷冻期): dp[i - 1][1];
        //dp[i][3](冷冻期后不持股): Math.max(dp[i - 1][3], dp[i - 1][2]);
        int len = prices.length;
        int[][] dp = new int[len][4];
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = 0;
        dp[0][3] = 0;
        for(int i = 1; i < len; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][3], dp[i - 1][2]) - prices[i]);
            dp[i][1] = dp[i - 1][0] + prices[i];
            dp[i][2] = dp[i - 1][1];
            dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2]);
        }
        return Math.max(dp[len - 1][1], Math.max(dp[len - 1][2], dp[len - 1][3]));
    }

    //42.最长递增子序列
    public int lengthOfLIS(int[] nums) {
        //dp[i]: 以 nums[i] 为结尾的，最长严格递增子序列长度
        //dp[i] = Math.max(dp[j] + 1, dp[i]);
        int len = nums.length;
        int[] dp = new int[len];
        Arrays.fill(dp, 1);
        int result = 1;
        for(int i = 1; i < len; i++) {
            for(int j = 0; j < i; j++) {
                if(nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
            result = result > dp[i] ? result : dp[i];
        }
        return result;
    }

    //43.最长连续递增序列
    public int findLengthOfLCIS(int[] nums) {
        //dp[i]: 以 nums[i] 为结尾的最长连续递增序列
        int len = nums.length;
        int[] dp = new int[len];
        Arrays.fill(dp, 1);
        int result = 1;
        for(int i = 1; i < len; i++) {
            if(nums[i - 1] < nums[i]) {
                dp[i] = dp[i - 1] + 1;
            }
            result = result > dp[i] ? result : dp[i];
        }
        return result;
    }

    //44.随机链表的复制
    public Node copyRandomList(Node head) {
        Node dummy = new Node(0);
        Node cur = dummy;
        Node cur2 = head;
        Map<Node, Node> map = new HashMap<>();
        //1.先用 map 记录一遍
        while(cur2 != null) {
            Node node = new Node(cur2.val);
            cur.next = node;
            cur = cur.next;
            map.put(cur2, cur);
            cur2 = cur2.next;
        }
        //2.写随机指针
        cur = dummy.next;
        cur2 = head;
        while(cur != null) {
            Node target = map.get(cur2.random);
            cur.random = target;
            cur = cur.next;
            cur2 = cur2.next;
        }
        return dummy.next;
    }

}

class Main {
    //测试
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] coins = {1,2,5};
        int amount = 11;
        solution.coinChange(coins, amount);
    }
}
>>>>>>> ff3f488e325d7766c3bd91ad5d1691e123de9b38:solution1/demo_2023_10/Solution.java
